نظریه‌ی گراف

نظریه‌ی گراف از ابتدا یکی از ابزارهای مهم و کاربردی در حل مسائل و توسعه‌ی علوم کامپیو‌تر بوده است. بنا بر این آشنایی با آن برای علاقمندان به علوم کامپیو‌تر و طراحی الگوریتم مفید و حتی لازم است. اما نظریه‌ی گراف چیست؟ برای پاسخ به این پرسش خوب است نگاهی کوتاه به تاریخچه و منشأ پیدایش نظریه‌ی گراف بیاندازیم.

شاید بتوان برای نظریه‌ی جوان گراف بر خلاف بسیاری از شاخه‌های دیگر علم ریاضی تاریخ تولد نسبتاً دقیقی در نظر گرفت. داستان این تولد باشکوه این گونه بود که در قرن هجدهم میلادی، مسئله‌ای فکر بعضی از مردم شهر کونیگسبرگ (کالینِنگراد کنونی در روسیه) را به خود مشغول کرده بود. موضوع از این قرار بود که رودخانه‌ای به نام پرِگِل از وسط شهر رد می‌شد و شهر را به دو نیمه تقسیم کرده بود. خود این رودخانه هم دارای دو جزیره‌ی نسبتاً بزرگ بود و این قسمت‌ها همگی به وسیله‌ی ۷ پل به شکل زیر به هم مرتبط بودند:

مسئله‌ای که در شهر مطرح شده بود این بود: آیا می‌توانیم از نقطه‌ای در شهر شروع به قدم زدن کنیم طوری که در انتها از روی هر کدام از پل‌ها دقیقاً یک بار رد شده باشیم؟ دقت کنید که شخص در این حالت مثلاً مجاز نبود که نصف یک پل را طی کند، سپس برگردد و بعداً نصف دیگر پل را از سر دیگرش بپیماید. به عبارتی شخص باید طی قدم زدن خود دقیقاً یک بار از هر نقطه‌ی هر پل می‌گذشت. این مسئله در تاریخ ریاضیات به عنوان مسئله‌ی هفت پل کونیگسبرگ مشهور است. لئونارد اویلر در مقاله‌ای به سال ۱۷۳۶ نشان داد که چنین کاری غیرممکن است. این مقاله‌ی اویلر را در تاریخ ریاضیات به عنوان شالوده‌ی نظریه‌ی گراف و همچنین پیشاهنگ توپولوژی به حساب می‌آورند. اما اویلر این مسئله را چگونه حل کرد؟

اویلر (درست مثل یک ریاضیدان واقعی!) نخست کوشید مدلی از این مسئله ارائه کند. وی دو قسمت شهر و دو جزیره را با نقاطی نمایش داد و هر پل بین دو قسمت را با خطی میان نقاط متناظر با آن‌ها:

شکل سمت راست یعنی مدل ساده‌شده‌ی شهر، چیزی نیست جز نمایش گرافیِ خشکی‌ها و پل‌های شهر. این شکل شبیه به اَشکال هندسی است اما تفاوت بسیار مهمی با این اشکال دارد: در نمایش یک گراف، مختصات نقاط یا فاصله‌ی آن‌ها نسبت به هم یا طول و شکل و انحنای خطوط تقریباً هیچ اهمیتی برای ما ندارند. تنها چیزی که مهم است این است که نقاط (که هر کدامشان اغلب نشانگر یک شیء یا مکان واقعی‌اند) به یکدیگر متصل شده‌اند یا نه. به عبارتی گراف یک ساختار از ارتباط‌ها ست. در هر مسئله‌ای که شما با ارتباط یا عدم ارتباط میان برخی اشیاء یا موجودات سر و کار داشتید، حواستان باشد که گراف ممکن است به کارتان آید.

حال به مسئله‌ی اصلی برگردیم و ببینیم اویلر چگونه در مورد این مسئله استدلال کرد. نخست باید پرسید اگر بخواهیم مسئله‌ی اصلی‌مان، یعنی قدم زدن در شهر، را روی مدل سمت راست در نظر بگیریم به چه مسئله‌ای می‌رسیم؟ به این مسئله می‌رسیم که ما می‌خواهیم در گراف بالا از یک نقطه شروع کنیم و از روی هر خط دقیقاً یک بار رد شویم. آیا این مسئله برایتان آشنا نیست؟! آیا شبیه به آن مسائل سرگرم‌کننده‌ای نیست که شکلی را به ما می‌دادند و می‌پرسیدند که آیا می‌توانیم بدون بلند کردن قلم از روی کاغذ و بدون آنکه خطی را دوبار بکشیم، آن شکل را رسم کنیم؟ این دقیقاً مسئله‌ای از‌‌ همان نوع است. پس اگر استدلال اویلر در مسئله‌ی هفت پل کونیگسبرگ را یاد بگیریم، راه‌حل این مسائل را هم خواهیم آموخت.

استدلال اویلر مبتنی بر یک ایده‌ی ساده و سرراست بود: به غیر از نقطه‌ی شروع و نقطه‌ی پایان، بقیه‌ی نقاط شکل از این قاعده تبعیت می‌کنند: ما هر‌گاه از طریق یک خط (یا پل) به یک نقطه وارد شویم، باید از طریق خطی دیگر از آن نقطه خارج شویم. پس در نخستین ورود و خروج ما به یک نقطه، دو خط به آن متصل می‌شوند. اگر یک بار دیگر بخواهیم به همین نقطه وارد شویم، باید از خط جدیدی وارد شده و از خط دیگری هم خارج شویم. با این کار دو خط دیگر به این نقطه افزوده می‌شوند و سرجمع می‌شود چهار خط؛ و الی آخر. پس اویلر نتیجه گرفت که ما فقط در صورتی می‌توانستیم راه‌حلی موفقیت‌آمیز برای این مسئله بیابیم که غیر از دو نقطه در گراف (که تبدیل به نقاط آغاز و پایان ما می‌شدند) به بقیه‌ی نقاط تعداد زوجی خط وصل می‌بود. این در حالی است که با نگاهی به گراف واضح می‌شود که به هر چهار نقطه تعداد فردی خط متصل است. بنابراین نمی‌شود گراف بالا را بدون برداشتن قلم از روی کاغذ و بدون اینکه از خطی که قبلاً کشیده‌ایم رد شویم، رسم کرد. مانند این است که بگوییم نمی‌شود از یک نقطه در شهر شروع به قدم زدن کرد و با دقیقاً یک بار گذشتن از هر پل به پیاده‌روی خود پایان داد.

خوب است در اینجا چند اصطلاح ساده‌ی نظریه‌ی گراف را معرفی کنیم: در نظریه‌ی گراف به نقاط دایره‌ای شکلی که در گراف بالا هر کدام نماینده‌ی یکی از خشکی‌های نقشه‌ی شهر بودند، یک رأس یا گره می‌گوییم؛ به هر خطی که دو رأس را به هم متصل می‌کند، یال یا لبه می‌گوییم. و در ‌‌نهایت تعداد یال‌های متصل به یک رأس را، درجه‌ی آن رأس می‌نامیم. بنابراین در گراف فوق، درجه‌ی سه تا از رأس‌ها (رأسهای سمت راست و پایین و بالا) سه است و درجه‌ی رأس سمت چپ پنج است. پس قدم‌زنی یا گشتی با ویژگی‌های فوق که مدّ نظر مردم کونیگسبرگ بوده، تنها در شهر یا منطقه‌ای قابل انجام است که اگر گراف آن را رسم کنیم یا درجه‌ی تمام رئوس زوج باشد و یا فقط درجه‌ی دو رأس فرد و بقیه زوج باشد.

ما در اینجا کوشیدیم با معرفی مسئله‌ی پل‌های کونیگسبرگ و استدلال اویلر شما را با نظریه‌ی گراف آشنا کنیم. این مسئله‌ای بود ساده، در حالی که در علوم کامپیو‌تر و علوم دیگر، ما اغلب گراف را برای مدلسازی‌های پیچیده‌تر و گاهی بسیار پیچیده به کار می‌بریم که نیازمند داده‌ساختارهای دقیق است و حل آن‌ها نیز نیازمند الگوریتم‌هایی نسبتاً دشوار است. مثلاً در علوم کامپیو‌تر گراف را برای مدلسازی شبکه‌های ارتباطات، سازماندهی داده‌ها، دستگاه‌های محاسباتی، طراحی چیپ‌های کامپوتری و غیره به کار می‌برند. حل مسائل گراف در این زمینه‌ها نیازمند آَشنایی و تسلط بر الگوریتم‌های گراف در زمینه‌هایی نظیر شمارش، همریختی، مسئله‌ی خوشه‌ و مسئله‌ی مجموعه‌ی مستقل، رنگ‌آمیزی گراف‌ها (نظیر مسئله‌ی معروف چهاررنگ) مسائل مربوط به مسیرهای بهینه، شارش‌های شبکه، مسائل پوشش و غیره است. همچنین جالب است بدانید که نظریه‌ی گراف علاوه بر علوم کامپیو‌تر در گستره‌ی وسیعی از فیزیک ماده‌ی چگال گرفته تا علم زبان‌شناسی (زبان‌شناسی محاسباتی و معنا‌شناسی لغت‌نامه‌ای) و جامعه‌شناسی (تحلیل شبکه‌ی اجتماعی) کاربرد دارد.